class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    /*
    缺失的数一定在1-n或者n+1
    把每个元素放在它应该在的位置，比如1应该在0号位置，2应该在1位置
    即num[i]应该在num[i]-1号位置，swap(num[i],num[num[i]-1])
    对于元素值不在1-n范围内的不用管它
    值在1-n范围内元素都在它该呆的位置上之后，再遍历一遍数组，如果发现有元素出现在它不该出现的
    位置上，返回该位置
    否则返回n+1
    */
    int minNumberDisappeared(vector<int>& nums) {
        // write code here
        for(int i=0;i<nums.size();i++)
        {
            while(nums[i]>0&&nums[i]<nums.size()&&nums[i]!=i+1)
                swap(nums[i], nums[nums[i]-1]);
        }
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]!=i+1)
                return i+1;
        }
        return nums.size()+1;
    }
};